package com.qz.sort;

import sun.font.FontRunIterator;

import javax.annotation.PreDestroy;
import javax.crypto.KeyGenerator;
import java.util.Arrays;
import java.util.Random;

/**
 * @Description
 * @Author Flag
 * @Date: 2021/8/1 16:17
 * @Version: 1.0
 **/
public class QuickSortDome {
    public static void main(String[] args) {
        int[] array = {51,74,74,78,72,71,161,61,31,99,66};

//        System.out.println();
//        QuickSort quickSort = new QuickSort(array);
//        quickSort.quickSort(0,array.length-1);
//        quickSort.show();
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");

        }
    }


    public static void quickSort(int[] array,int left,int right){
        int l = left;
        int r = right;
        int pivot = array[(left+right)/2];
        int temp;
        //while循环的目的
        while (l<r){
            //再左边一直找
            while (array[l]<pivot ){
                l++;
            }

            while (array[r] > pivot){
                r--;
            }

            //交换

            if(l >=r ){
                break;
            }
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;

            if(array[l] == pivot){
                r--;
            }

            if(array[r] == pivot){
                l++;
            }
            if(l==r){
                l++;
                r--;
            }

            if(left < r){
                quickSort(array,left,r);
            }

            if(right > l){
                quickSort(array,l,right);
            }



        }

    }





}


class QuickSort{
    private static int[] array;

    public QuickSort(int[] array) {
        this.array = array;
    }

    public static int[] sort(int[] array,int left,int right){
        QuickSort.array = array;
        quickSort(left,array.length-1);
        return QuickSort.array;
    }


    /**
     * 从小到大
     * @param left
     * @param right
     * @return
     */
    public static void quickSort(int left,int right){

        if(left > right){
            return;
        }

        //表示左指针的位置
        int l = left;
        //表示右指针的位置
        int r = right;
        //定义头部为基准元素
        int head = array[left];

        int temp;

        // l<r 证明两个指针没有相交
        while (l != r){

            //判断当前元素和基准元素的关系,因为是从小到大，所以要求右侧的元素大于基准元素，否则就停下来
            while (array[r] >= head && l < r) {
                r--;
            }

            while (array[l] <= head && l < r){
                l++;
            }

            //交换位置
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;
        }

        //
        array[left] = array[l];
        array[l] = head;


        quickSort(left,l-1);
        quickSort(l+1,right);
    }


    public void show(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

